/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.wip.graph.algo;

import combi.graph.Mask;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Map.Entry;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import combi.graph.algo.Ksp_Yen;

import org.jgrapht.GraphPath;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.ext.DOTExporter;
import org.jgrapht.ext.EdgeNameProvider;
import org.jgrapht.ext.IntegerNameProvider;
import org.jgrapht.ext.StringNameProvider;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.DirectedMaskSubgraph;

import combi.wip.sipper.io.dot.DOTColorEdgeNameProvider;
import combi.wip.sipper.io.dot.DOTColorExporter;
import combi.wip.sipper.io.dot.DOTColorVertexNameProvider;
import combi.wip.sipper.io.dot.VertexAlternateNameProvider;

import combi.utils.Couple;

/*
 * Calcul d'une hierarchie entre genes sur le modele integre selon la distance minimale entre genes.
 * A chaque gene est associe l'ensemble de ses sommets dans le modele integre.
 * On obtient un arbre en sortie.
 */

public class HierarchieCouvrante {

	//private static String workspace = "./ecocyc - ALL-CHORISMATE-PWY - 53/";
	//private static String workspace = "./ecocyc/";
	//private static String workspace = "./data/";
	//private static String workspace = "./eco/";
	private static String workspace = System.getProperty("user.home") + "/Data/Chili/meta_reaction/";

	//private static String workspace = "./eco00010/";
	//private static String pathOutput = "./" + java.lang.System.currentTimeMillis() + "/";
	//private static String modeleFile = "modele.txt";
	//private static String modeleFile = "eco00010.txt";
	private static String modeleFile = "modele.txt";

	private static Integer k = 1;

	static String associationsFile = workspace + "associations.txt";
	static String associationsRFile = workspace + "associationsR.txt";
	static String associationsGFile = workspace + "associationsG.txt";
	//static String associationsMFile = workspace + "associationsM.txt";
	//static String associationsFile = workspace + "associations_eco00010.txt";
	//static String associationsRFile = workspace + "associationsR_eco00010.txt";
	//static String associationsGFile = workspace + "associationsG_eco00010.txt";
	//static String associationsMFile = workspace + "associationsM_eco00010.txt";

	private static DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> modele;

	/*
	 *  Chargement du modele
	 */

	private static DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> loadModele(String fileIn)
	{
		//String fileIn = "data/test_50";
		Date mid = null ;
		DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> graph = new DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		BufferedReader in;
		try{


			in = new BufferedReader (new FileReader (fileIn));
			// ajout sommets
			String ch = in.readLine();
			Integer number = Integer.valueOf(ch);
			for (int i=0; i<number;i++)
			{
				graph.addVertex((Integer)i);
			}

			//ajout arcs
			Matcher m;
			//String tag = "(?:([0-9]+)\\s+([0-9]+)\\s+((?:[0-9]+(?:\\.[0-9]+)?)))";
			String tag = "(?:([0-9]+)\\s+([0-9]+)\\s+(.+))";
			Pattern reco = Pattern.compile(tag);
			int j = 0;
			while ((ch = in.readLine()) != null)
			{
				try
				{
					m = reco.matcher(ch);
					while (m.find())
					{
						Integer src = Integer.valueOf(m.group(1));
						Integer dest = Integer.valueOf(m.group(2));
						Double poids = Double.valueOf(m.group(3));
						graph.addEdge(src, dest);
						graph.setEdgeWeight(graph.getEdge(src, dest), poids);
						j++;
					}
				}
				catch (Exception e)
				{
					e.printStackTrace();
				}
			}
			//System.err.println(graph);
			// filtrage des sommets isoles

		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
		return graph;
	}

	private static Map<String, Set<Integer>> loadAssoReaction(String fileIn) throws IOException
	{
		return loadAsso(fileIn, "(?:(.+)\\t(.+))");
	}

	private static Map<String, Set<Integer>> loadAssoGene(String fileIn) throws IOException
	{
		return loadAsso(fileIn, "(?:(.+)\\t(.+))");
	}

	private static Map<String, Set<Integer>> loadAsso(String fileIn, String tag) throws IOException
	{
		Map<String, Set<Integer>> result = new HashMap<String, Set<Integer>>();
		BufferedReader in = new BufferedReader (new FileReader (fileIn));
		Matcher m;
		Matcher m2;
		String nb = "(?:([0-9]+))";
		Pattern reco = Pattern.compile(tag);
		Pattern recoNb = Pattern.compile(nb);
		String ch;
		while ((ch = in.readLine()) != null)
		{
			try
			{
				m = reco.matcher(ch);
				while (m.find())
				{
					Set<Integer> set = new HashSet<Integer>();
					result.put(m.group(1), set);
					m2 = recoNb.matcher(m.group(2));
					while (m2.find())
					{
						set.add(Integer.valueOf(m2.group(1)));
					}
				}
			}
			catch (Exception e)
			{
				e.printStackTrace();
			}
		}
		in.close();
		return result;
	}

	public static void main(String[] args) {


		Date deb = new Date(java.lang.System.currentTimeMillis());

		//File fb = new File(workspace+pathOutput); 
		//fb.mkdirs(); 
		String fileIn = workspace+modeleFile;

		modele = loadModele(fileIn);

		/*
		 * Chargement des associations element(gene) -> sommets
		 */

		Map<String, Set<Integer>> reactionsAsso = new HashMap<String, Set<Integer>>();
		Map<String, Set<Integer>> genesAsso = new HashMap<String, Set<Integer>>();
		Map<String, Set<Integer>> metabolitesAsso = new HashMap<String, Set<Integer>>();
		try {
			reactionsAsso = loadAssoReaction(associationsRFile);
			System.out.println(reactionsAsso);
			genesAsso =loadAssoGene(associationsGFile);
			System.out.println(genesAsso);

			//metabolitesAsso =loadAssoGene(associationsMFile);
			//System.out.println(metabolitesAsso);
			reactionsAsso.putAll(metabolitesAsso);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}



		/*
		 * Calcul de la hierarchie sans controle sur l'inclusion de chemins.
		 */

		{
			// 1- calcul de la distance minimale entre chaque couple de g�nes.
			// par une m�thode des plus courts chemins.


			Integer fakeSrc = -1;
			modele.addVertex(fakeSrc);

			Integer fakeDest = -2;
			modele.addVertex(fakeDest);

			Map<Couple<String, String>, Double> distances = new HashMap<Couple<String, String>, Double>();
			SortedSet<Couple<Couple<String, String>, Double>> distancesL = new TreeSet<Couple<Couple<String, String>, Double>>(new CompareCouple2());
			int nb = 0;
			for (Entry<String, Set<Integer>> entry1 :genesAsso.entrySet())
			{
				nb++;
				// ajout des sources fakes
				for (Integer src : entry1.getValue())
				{
					modele.addEdge(fakeSrc, src);
					modele.setEdgeWeight(modele.getEdge(fakeSrc, src), 0);
				}
				for (Entry<String, Set<Integer>> entry2 :genesAsso.entrySet())
				{
					if (!entry1.getKey().equals(entry2.getKey()))
					{
						//ajout des dest fakes
						for (Integer dest : entry2.getValue())
						{
							modele.addEdge(dest, fakeDest);
							modele.setEdgeWeight(modele.getEdge(dest, fakeDest), 0);
						}
						if (k==1)
						{

							// plus courts chemins
							DijkstraShortestPath<Integer, DefaultWeightedEdge> dijkstra = new DijkstraShortestPath<Integer, DefaultWeightedEdge>(modele, fakeSrc, fakeDest);
							distances.put(new Couple<String, String>(entry1.getKey(), entry2.getKey()),dijkstra.getPathLength());
							distancesL.add(new Couple<Couple<String, String>, Double>(new Couple<String, String>(entry1.getKey(), entry2.getKey()),dijkstra.getPathLength()));
						}
						else{
							// k plus courts chemins
							Mask<Integer, DefaultWeightedEdge> mask = new Mask<Integer, DefaultWeightedEdge>();
							DirectedMaskSubgraph<Integer, DefaultWeightedEdge> mod = new DirectedMaskSubgraph<Integer, DefaultWeightedEdge>(modele, mask);

							Ksp_Yen<Integer, DefaultWeightedEdge> algo = new Ksp_Yen<Integer, DefaultWeightedEdge>(mod, fakeSrc, fakeDest, k);
							Thread t = new Thread(algo);
							t.start();

							while (t.isAlive())
							{}
							if (!algo.getPaths().isEmpty())
							{
								Double poids = 0.0;
								// ajout pour calcul poids sous-graphe
								DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> tempG = new DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge>(DefaultWeightedEdge.class);
								for (GraphPath<Integer,DefaultWeightedEdge> ch : algo.getPaths())
								{
									for(DefaultWeightedEdge e : ch.getEdgeList())
									{
										tempG.addVertex(modele.getEdgeSource(e));
										tempG.addVertex(modele.getEdgeTarget(e));

										tempG.addEdge(modele.getEdgeSource(e),modele.getEdgeTarget(e));
										tempG.setEdgeWeight(tempG.getEdge(modele.getEdgeSource(e),modele.getEdgeTarget(e)),modele.getEdgeWeight(e));

									}
								}
								for (DefaultWeightedEdge e :tempG.edgeSet())
								{
									poids = poids + tempG.getEdgeWeight(e);
								}
								distances.put(new Couple<String, String>(entry1.getKey(), entry2.getKey()),poids);
								distancesL.add(new Couple<Couple<String, String>, Double>(new Couple<String, String>(entry1.getKey(), entry2.getKey()),poids));
							}
							else
							{
								distances.put(new Couple<String, String>(entry1.getKey(), entry2.getKey()),Double.POSITIVE_INFINITY);
								distancesL.add(new Couple<Couple<String, String>, Double>(new Couple<String, String>(entry1.getKey(), entry2.getKey()),Double.POSITIVE_INFINITY));				
							}
						}
						//retrait dest fakes
						for (Integer dest : entry2.getValue())
						{
							modele.removeEdge(dest, fakeDest);
						}
					}
				}
				//retrait sources fakes
				for (Integer src : entry1.getValue())
				{
					modele.removeEdge(fakeSrc, src);
				}
				System.out.println(nb*100/genesAsso.size()+"% : " + new Date(java.lang.System.currentTimeMillis()));
			}
			//System.out.println(distancesL);

			try {
				BufferedWriter out = new BufferedWriter(new FileWriter(workspace + "hierarchie.txt"));
				//out.write(" ");
				/*
				for(String g1 : genesAsso.keySet())
				{
					out.write( "\t" +g1 );
				}
				 */
				out.write(""+nb);
				out.write( "\n" );
				for(String g1 : genesAsso.keySet())
				{
					out.write(g1+"          ");
					for(String g2 : genesAsso.keySet())
					{
						if(g1 == g2)
						{
							out.write(" 0");
						}
						else
						{
							Double d = Math.min(distances.get(new Couple<String, String>(g1, g2)), distances.get(new Couple<String, String>(g2, g1)));
							if (d.isInfinite())
							{
								out.write(" " + Long.MAX_VALUE);
							}
							else
							{
								out.write(" " + d.longValue());
							}
						}
					}
					out.write( "\n" );
				}
				out.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

			// 2- mise en place de la hierarchie.
			// par un arbre couvrant l'ensemble des distances entre couples de genes.

			Map<String, String> hierarchieFils2PereMap = new HashMap<String, String>();
			Map<String, Double> hierarchiePoidsNoeudsMap = new HashMap<String, Double>();
			Map<String, Set<String>> hierarchiePere2FilsMap = new HashMap<String, Set<String>>();
			for (String s : genesAsso.keySet())
			{
				hierarchiePoidsNoeudsMap.put(s, 0.0);
			}

			Integer newpere = 0;
			for (Couple<Couple<String, String>, Double> c : distancesL)
			{
				ajouteNoeud(hierarchieFils2PereMap, hierarchiePere2FilsMap, hierarchiePoidsNoeudsMap, c.getFirst().getFirst(), c.getFirst().getSecond(), c.getSecond(), newpere++);
			}
			System.out.println(hierarchieFils2PereMap);
			exportHierarchie(hierarchieFils2PereMap, hierarchiePoidsNoeudsMap);
		}

		/*
		 * Mise en evidence des operons entre-eux
		 */
	}

	private static class ComparePeres<E> implements Comparator<E>
	{
		Map<E, Double> poids;

		public ComparePeres(Map<E, Double> poids)
		{
			this.poids = poids;
		}

		@Override
		public int compare(E o1, E o2) {
			return poids.get(o1).compareTo(poids.get(o2));
		}

	}

	private static void ajouteNoeud(Map<String, String> hierarchieFils2PereMap,
			Map<String, Set<String>> hierarchiePere2FilsMap,
			Map<String, Double> hierarchiePoidsNoeudsMap, String first,
			String second, Double poids, Integer newpere) {

		String pere1;
		Set<String> peres1 = new HashSet<String>();
		String pere2;
		Set<String> peres2 = new HashSet<String>();

		pere1 = first;
		peres1.add(pere1);
		while(hierarchieFils2PereMap.containsKey(pere1))
		{
			if (hierarchiePoidsNoeudsMap.get(pere1) <= poids)
			{
				pere1 = hierarchieFils2PereMap.get(pere1);
				peres1.add(pere1);
			}
		}

		pere2 = second;
		peres2.add(pere2);
		while(hierarchieFils2PereMap.containsKey(pere2))
		{
			if (hierarchiePoidsNoeudsMap.get(pere2) <= poids)
			{
				pere2 = hierarchieFils2PereMap.get(pere2);
				peres2.add(pere2);
			}
		}

		//System.err.println(peres1);
		//System.err.println(peres2);
		Set<String> tmp = new HashSet<String>(peres2);
		tmp.retainAll(peres1);
		if (tmp.isEmpty())
		{
			if (hierarchiePoidsNoeudsMap.get(pere1).equals(poids))
			{
				if(hierarchiePoidsNoeudsMap.get(pere2).equals(poids))
				{

					//System.err.println("p1=newpoids=p2");
					//RAS grace a l'ordre impose?

					//hierarchieFils2PereMap.put(pere2, pere1);
					for (String f : hierarchiePere2FilsMap.get(pere2))
					{
						hierarchieFils2PereMap.put(f, pere1);
					}
					hierarchiePere2FilsMap.get(pere1).addAll(hierarchiePere2FilsMap.get(pere2));
					hierarchiePere2FilsMap.get(pere2).clear();
					hierarchiePere2FilsMap.remove(pere2);
					//hierarchiePere2FilsMap.put(pere2, hierarchiePere2FilsMap.get(pere1));
				}
				else
				{
					//System.err.println("p1=newpoids>p2");
					//hierarchieFils2PereMap.put(pere2, pere1);
					hierarchiePere2FilsMap.get(pere1).add(pere2);

					hierarchieFils2PereMap.put(pere2, pere1);
					//hierarchiePere2FilsMap.put(pere2, hierarchiePere2FilsMap.get(pere1));
				}
			}
			else
			{
				if(hierarchiePoidsNoeudsMap.get(pere2) == poids)
				{
					//System.err.println("p1<newpoids=p2");

					hierarchiePere2FilsMap.get(pere2).add(pere1);

					hierarchieFils2PereMap.put(pere1, pere2);
				}
				else
				{
					//System.err.println("p1<newpoids>p2");
					hierarchieFils2PereMap.put(pere1, newpere.toString());
					hierarchieFils2PereMap.put(pere2, newpere.toString());
					hierarchiePoidsNoeudsMap.put(newpere.toString(), poids);
					Set<String> newFils = new HashSet<String>();
					newFils.add(pere1);
					newFils.add(pere2);
					hierarchiePere2FilsMap.put(newpere.toString(), newFils);
				}
			}
		}

	}

	private static void exportHierarchie(
			Map<String, String> hierarchieFils2PereMap,
			Map<String, Double> hierarchiePoidsNoeudsMap) {


		DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> graph = new DefaultDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class); 
		Map<String, String> alternateName = new HashMap<String, String>();
		Map<String, String> shape = new HashMap<String, String>();
		Map<String, String> couleur = new HashMap<String, String>();
		Map<String, Set<Integer>> gene2NumOperons = new HashMap<String, Set<Integer>>();

		try {
			int num_op = 0;
			//Map<String, Set<String>> operons = chargeEnsemble("Operons1.txt");
			Map<String, Set<String>> operons = new HashMap<String, Set<String>>();
			for(Entry<String, Set<String>> entry : operons.entrySet())
			{
				num_op ++;
				String color = "red";
				if(entry.getValue().size() == 1)
				{
					color = "purple";
				}
				for (String s : entry.getValue())
				{
					couleur.put(s, color);
					Set<Integer> nums = gene2NumOperons.get(s);
					if (nums == null)
					{
						nums = new HashSet<Integer>();
						gene2NumOperons.put(s, nums);
					}
					nums.add(num_op);
				}
			}

		} catch (Exception e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}

		for (Entry<String, String> entry : hierarchieFils2PereMap.entrySet())
		{

			if (!graph.containsVertex(entry.getKey()))
			{
				graph.addVertex(entry.getKey());
			}
			if (!hierarchiePoidsNoeudsMap.get(entry.getValue()).isInfinite())
			{
				if (!graph.containsVertex(entry.getValue()))
				{
					graph.addVertex(entry.getValue());
				}
				graph.addEdge(entry.getValue(), entry.getKey());
				graph.setEdgeWeight(graph.getEdge(entry.getValue(), entry.getKey()), hierarchiePoidsNoeudsMap.get(entry.getValue()));
				alternateName.put(entry.getValue(), hierarchiePoidsNoeudsMap.get(entry.getValue()).toString());
			}
			if (hierarchiePoidsNoeudsMap.get(entry.getKey()) == 0.0)
			{
				shape.put(entry.getKey(), "shape=rect");
				if (!couleur.containsKey(entry.getKey()))
				{
					couleur.put(entry.getKey(), "green");
				}
				if(gene2NumOperons.containsKey(entry.getKey()))
					alternateName.put(entry.getKey(), entry.getKey() + "\\n" + gene2NumOperons.get(entry.getKey()));
				
			}
		}

		DOTColorExporter<String, DefaultWeightedEdge> graphDOT = new DOTColorExporter<String, DefaultWeightedEdge>(new IntegerNameProvider<String>(), new DOTColorVertexNameProvider<String>(couleur, shape, alternateName),null);
		try {
			graphDOT.setRankDir("LR");
			graphDOT.export(new BufferedWriter(new FileWriter(workspace + "hierarchie" + ".dot")), graph);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}
	public static Map<String, Set<String>> chargeEnsemble(String fileIn) throws IOException
	{
		Map<String, Set<String>> modules = new TreeMap<String, Set<String>>();		
		BufferedReader in = new BufferedReader (new FileReader (fileIn));
		String modName = "(?:^([^\t]+)\t(.+)$)";
		String elem = "(?:[^\t ]+)";
		Matcher m;
		Matcher m2;
		Pattern recoMod = Pattern.compile(modName);
		Pattern recoElem = Pattern.compile("("+elem+")");
		String ch;
		while ((ch = in.readLine()) != null)
		{
			//System.err.println(ch);
			m = recoMod.matcher(ch);
			while (m.find())
			{
				String id = new String(m.group(1));
				//System.err.println(id);
				Set<String> set = new HashSet<String>();
				m2 = recoElem.matcher(m.group(2));
				while(m2.find())
				{
					String r = new String(m2.group(1));
					set.add(r);
				}
				if (!set.isEmpty())
				{
					modules.put(id, set);
				}
			}
		}
		in.close();
		return modules;
	}

	private static class CompareCouple2 implements Comparator<Couple<Couple<String, String>, Double>>
	{


		@Override
		public int compare(Couple<Couple<String, String>, Double> o1,
				Couple<Couple<String, String>, Double> o2) {
			int result = o1.getSecond().compareTo(o2.getSecond());
			if (result == 0)
			{
				result = o1.getFirst().getFirst().compareTo(o2.getFirst().getFirst());
			}

			if (result == 0)
			{
				result = o1.getFirst().getSecond().compareTo(o2.getFirst().getSecond());
			}
			return result;
		}


	}



}
